package leetcode;

import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.BlockingDeque;
import java.util.concurrent.LinkedBlockingDeque;
import java.util.concurrent.LinkedBlockingQueue;

/**
 * 143. 重排链表
 * 给定一个单链表 L：L0→L1→…→Ln-1→Ln ，
 * 将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…
 * 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
 * 示例 1:
 * 给定链表 1->2->3->4, 重新排列为 1->4->2->3.
 * 示例 2:
 * 给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.
 */

public class problems_142 {

    public static void main(String[] arge) {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        new Solution().reorderList(node1);
        System.out.println();
    }

    static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }

    static class Solution {
        public void reorderList(ListNode head) {
            if (null == head) return;
            // 生成队列
            BlockingDeque<ListNode> queue = new LinkedBlockingDeque<ListNode>(128);
            ListNode node = head;
            while (null != node.next) {
                queue.offer(node.next);
                node = node.next;
            }
            //
            try {
                ListNode linkNode = head;
                boolean bolFirst = false;
                ListNode nextNode = null;
                while (!queue.isEmpty()) {
                    nextNode = bolFirst ? queue.takeFirst() : queue.takeLast();
                    linkNode.next = nextNode;
                    linkNode = nextNode;
                    bolFirst = !bolFirst;
                }
                if(null != nextNode) nextNode.next = null;
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            System.out.println("");
        }
    }
}